package main

import "math"

func minimumTotal(triangle [][]int) int {
	//使用距离矩阵
	n := len(triangle)
	f := make([][]int, n)
	for i := 1; i <= n; i++ {
		f[i] = make([]int, n)
	}
	f[0][0] = triangle[0][0]
	for i := 1; i < n; i++ {
		//侧边点的路径
		f[i][0] = f[i-1][0] + triangle[i][0]
		for j := 1; j < i; j++ {
			f[i][j] = min(f[i-1][j-1], f[i-1][j]) + triangle[i][j]
		}
		f[i][i] = f[i-1][i-1] + triangle[i][i]
	}
	ans := math.MaxInt32
	for i := 0; i < n; i++ {
		ans = min(ans, f[n-1][i])
	}
	return ans
}

func min(i, j int) int {
	if i > j {
		return j
	} else {
		return i
	}
}

func main() {
	ii := [][]int{{2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}}
	total := minimumTotal(ii)
	println(total)
}
